public class BinaryTree {
        static class TreeNode{
            public int val;
            public TreeNode left;
            public TreeNode right;

            public TreeNode(int val) {
                this.val = val;
            }
        }
        public TreeNode root;//指向一个根节点
        public TreeNode createTree(){
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');

            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            E.right = H;
            return A;
        }

        public void preOrder(TreeNode root){
            if (root == null) {
                return;
            }
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }

        public void inOrder(TreeNode root){
            if (root == null) {
                return;
            }
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }


//        利用前序遍历和中序遍历创建二叉树
//        public int priIndex;
//        public TreeNode buildTree(int[] preorder,int[] inorder){
//            return buildTreeChild(preorder,inorder,0,inorder.length-1);
//        }
//        private TreeNode buildTreeChild(int[] preOrder,int[] inOrder ,int inBegin ,int inEnd){
//            //没有左子树或者右子树
//            if (inBegin > inEnd){
//                return null;
//            }
//            //创建根节点
//            TreeNode root = new TreeNode(preOrder[priIndex]);
//            //找到中序遍历中根节点的下标
//            int rootIndex = findIndex(inOrder,inBegin,inEnd,preOrder[priIndex]);
//            if (rootIndex == -1){
//                return null;
//            }
//            priIndex++;
//            //创建左子树和右子树
//            root.left = buildTreeChild(preOrder,inOrder,inBegin,rootIndex-1);
//            root.right = buildTreeChild(preOrder,inOrder,rootIndex+1,inEnd);
//            return root;
//        }
//        private int findIndex(int[] inOrder ,int inBegin ,int inEnd,int key){
//            for (int i = inBegin;i <= inEnd;i++){
//                if (inOrder[i] == key){
//                    return i;
//                }
//            }
//            return -1;
//        }



   //根据中序遍历和后序遍历构建二叉树
    public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] postorder,int[] inOrder ,int inBegin ,int inEnd){
        if (inBegin > inEnd){
            return null;
        }
        //创建根节点，前序遍历第一个就是其根节点
        TreeNode root = new TreeNode(postorder[postIndex]);
        //找到中序遍历中根节点的下标
        int rootIndex = findIndex(inOrder,inBegin,inEnd,postorder[postIndex]);
        if (rootIndex == -1){
            return null;
        }
        postIndex--;
        //创建左子树和右子树,先右后左
        root.right = buildTreeChild(postorder,inOrder,rootIndex+1,inEnd);
        root.left = buildTreeChild(postorder,inOrder,inBegin,rootIndex-1);
        return root;
    }
    private int findIndex(int[] postorder ,int inBegin ,int inEnd,int key){
        for (int i = inBegin;i <= inEnd;i++){
            if (postorder[i] == key){
                return i;
            }
        }
        return -1;
    }
}